import java.util.List;

class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
          int m = triangle.size() ;
          int n = triangle.get(m-1).size() ;
          int[][] dp = new int[m+1][n+1];
           for(int i=1 ; i <= n ; i ++){
             dp[1][i] = Integer.MAX_VALUE; 
          }
          dp[1][1] = triangle.get(0).get(0) ; 
          for(int i=2 ; i <= m ; i ++){
            for(int j=1 ; j<= i ; j ++){
                if(j == 1){
                  dp[i][j] = dp[i-1][j] + triangle.get(i-1).get(j-1) ; 
                }else if(j == i){
                    dp[i][j] = dp[i-1][j-1] + triangle.get(i-1).get(j-1) ; 
                }else{
                   dp[i][j] = Math.min(dp[i-1][j] , dp[i-1][j-1]) + triangle.get(i-1).get(j-1) ; 
                }
            }
          }
          int min = Integer.MAX_VALUE;
          for(int i=1 ; i <= n ; i ++){
            min = Math.min(min , dp[m][i]) ; 
          }
        return min ;

    }
}